package leetcode_900;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *@author 周杨
 *SumOfDistancesInTree_834_ 求一颗N叉树的每个节点到其他节点的总距离
 *describe:找规律 然后用DFS AC 33% 非常巧妙
 *see:https://leetcode.com/problems/sum-of-distances-in-tree/solution/
 *2018年10月31日 上午11:12:44
 */
public class SumOfDistancesInTree_834_ {
	int[] ans, count;
	List<Set<Integer>> graph;
	int N;

	public int[] sumOfDistancesInTree(int N, int[][] edges) {
		this.N = N;
		graph = new ArrayList<Set<Integer>>();
		ans = new int[N];
		count = new int[N];
		Arrays.fill(count, 1);

		for (int i = 0; i < N; ++i)
			graph.add(new HashSet<Integer>());
		for (int[] edge : edges) {
			graph.get(edge[0]).add(edge[1]);
			graph.get(edge[1]).add(edge[0]);
		}
		dfs(0, -1);
		dfs2(0, -1);
		return ans;
	}

	public void dfs(int node, int parent) {
		for (int child : graph.get(node))
			if (child != parent) {//不会走回来的路
				dfs(child, node);
				count[node] += count[child];
				ans[node] += ans[child] + count[child];
			}
	}

	public void dfs2(int node, int parent) {
		for (int child : graph.get(node))
			if (child != parent) {
				ans[child] = ans[node] - count[child] + N - count[child];
				dfs2(child, node);
			}
	}
}
